class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        n = len(nums)
        nums.sort()
        ans = list()
        for first in range(n):
            # 需要和上一次枚举的数不相同
            if first > 0 and nums[first] == nums[first-1]:
                continue
            third = n-1
            target = -nums[first]
            for second in range(first+1, n):
                if second > first + 1 and nums[second] == nums[second-1]:
                    continue
                # 需要保证b的指针在c的指针的左侧
                while second < third and nums[second] + nums[third] > target:
                    third -= 1
                # 指针重合，结束
                if second == third:
                    break
                if(nums[second] + nums[third] == target):
                    ans.append([nums[first], nums[second], nums[third]])
        return ans
nums = [-1,0,1,2,-1,-4]
example = Solution()
print(example.threeSum(nums))